package leetcode.lt100;

import java.util.ArrayList;
import java.util.List;

class Solution_93 {

    public static void main(String[] args) {
        String s = "19216811";
        new Solution_93().restoreIpAddresses(s);
    }

    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        List<String> temp = new ArrayList<>();
        dfs(s, 0, temp, res);
        return res;
    }

    private void dfs(String s, int start, List<String> temp, List<String> res) {
        int length = s.length();
        //找齐四位数
        if (temp.size() == 4) {
            if (start == length) {
                res.add(String.join(".", temp));
            }
            return;
        }
        //剪枝
        int restLength = length - start;
        int restNum = 4 - temp.size();
        if (restNum > restLength || restNum * 3 < restLength) {
            return;
        }
        for (int i = 0; i < 3 && start + i + 1 <= length; i++) {
            String substring = s.substring(start, start + i + 1);
            Integer value = Integer.valueOf(substring);
            //出现0开头非一位数
            if (value < 10 && i > 0) {
                return;
            }
            //超ip数值限制
            if (i == 2 && value > 255) {
                return;
            }
            if (substring.equals("92")) {
                System.out.println();
            }
            temp.add(substring);
            dfs(s, start + i + 1, temp, res);
            temp.remove(temp.size() - 1);
        }
    }

}